package StringParctice;

import java.util.HashSet;
import java.util.Set;

public class LengthOfLongestSubstring {
    /**
     * 3. 无重复字符的最长子串
     * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
     * <p>
     * <p>
     * <p>
     * 示例 1:
     * <p>
     * 输入: s = "abcabcbb"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
     * 示例 2:
     * <p>
     * 输入: s = "bbbbb"
     * 输出: 1
     * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
     * 示例 3:
     * <p>
     * 输入: s = "pwwkew"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     * 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
     */
    //1.暴力法解决无重复字符的最长字串问题
    public int lengthOfLongestSubstring(String s) {
        int length = s.length();
        int maxLength = 0;
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if (isContainsChar(s, i, j)) {
                    maxLength = Math.max(maxLength, j - i);
                }
            }
        }
        return maxLength;
    }

    private boolean isContainsChar(String s, int start, int end) {
        Set<Character> characterSet = new HashSet<>();
        for (int i = start; i < end; i++) {
            char charAt = s.charAt(i);
            if (characterSet.contains(charAt)) {
                return false;
            }
            characterSet.add(charAt);
        }
        return true;
    }

    //2.使用滑动窗口来实现
    public int lengthOfLongestSubstring_1(String s) {
        int length = s.length();
        Set<Character> characterSet = new HashSet<>();
        int maxLength = 0, start = 0, end = 0;
        while (start < length && end < length) {
            char ch = s.charAt(end);
            if(!characterSet.contains(ch)){
                characterSet.add(ch);
                end++;
                maxLength = Math.max(maxLength,end-start);
            }else{
                characterSet.remove(s.charAt(start++));
            }
        }
        return maxLength;
    }


    public static void main(String[] args) {
        LengthOfLongestSubstring lengthOfLongestSubstring = new LengthOfLongestSubstring();
        int abcabcbb = lengthOfLongestSubstring.lengthOfLongestSubstring_1("pwwkew");
        System.out.println(abcabcbb);
    }
}
